package writtenTraining.day42;

import java.util.*;

/**
 * day42:(1)模拟+ 贪心：MT1 最大差值
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param n int整型 
     * @return int整型
     */
    public int getDis (int[] A, int n) {
        // 模拟 + 贪心
        int INF = 0x3f3f3f3f;
        int ret = -INF;

        int min = A[0];
        for(int i = 0; i < n; i++) {
            ret = Math.max(ret,A[i] - min);
            // 贪前面的小值
            min = Math.min(min,A[i]);
        }

        return ret;
    }
}


/**
 * day42：(2)动态规划 + 完全背包问题：DP44 兑换零钱
 */

 class Main2 {
    public static void main(String[] args) {
        // 动态规划 + 完全背包问题

        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), aim = in.nextInt();
        int[] nums = new int[n+1];
        for(int i = 1; i <= n; i++) {
            nums[i] = in.nextInt();
        }

        //创建dp
        int[] dp = new int[aim+1];
        // 初始化
        int INF = 0x3f3f3f3f;
        Arrays.fill(dp,INF);
        dp[0] = 0;

        // 个数
        for(int i = 1; i <= n; i++) {
            for(int j = nums[i]; j <= aim; j++) {
                /**
                 * 注意， 注意， 注意 ! ! !
                 */
                // 如果装不下就继承前面的。否则就加上上一位的
                dp[j] = Math.min(dp[j  - nums[i]] + 1,dp[j]);
            }
        }

        System.out.println(dp[aim] >= INF ? -1 : dp[aim]);
    }

}

/**
 * day42:(3)滑动窗口 + 前缀和思想：小红的子串
 */



 class Main3 {
    public static void main(String[] args) {
//         滑动窗口 + 前缀和思想
//        前缀和思想：  【l,r】 = 【1,r】 - 【1,l - 1】
        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), l = in.nextInt(), r = in.nextInt();
        char[] chs = in.next().toCharArray();

//         先计算 【1，l - 1】
        long count1 = count(chs,l - 1);

//         最后计算 【1,r】
        long count2 = count(chs,r);

//         输出结果
        System.out.println(count2 - count1);
    }

    public static long count(char[]chs,int t) {
        long ret = 0L;
        int n = chs.length;
        Map<Character,Integer> map = new HashMap<>();
        for(int left = 0, right = 0; right < n; right++) {
            // 入窗口
            map.put(chs[right]
                    ,map.getOrDefault(chs[right],0) + 1);

            // 出窗口
            while(map.size() > t) {
                map.put(chs[left],map.get(chs[left]) - 1);
                // 如果种类为 0 就删去
                if(map.get(chs[left]) <= 0) {
                    map.remove(chs[left]);
                }
                left++;
            }
            //             更新结果
            ret += (right - left + 1);

        }

        return ret;
    }
}